//链表相交
class Solution {
public:
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        int s1=0,s2=0;
        ListNode*cur1=headA;
        ListNode*cur2=headB;
        while(cur1)
        {
            s1++;
            cur1=cur1->next;
        }
        while(cur2)
        {
            s2++;
            cur2=cur2->next;
        }
        if(cur1!=cur2) return nullptr;
        cur1=headA,cur2=headB;
        int sub=s1>s2?s1-s2:s2-s1;
        if(s1>s2)
        {
            while(sub--)
            {
                cur1=cur1->next;
            }
        }
        else
        {
            while(sub--)
            {
                cur2=cur2->next;
            }
        }
        while(cur1 && cur2)
        {
            if(cur1==cur2) return cur1;//注意这里比的不是数据 而是整个节点
            cur1=cur1->next;
            cur2=cur2->next;
        }
        return nullptr;
    }
  
};
//环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast) return true;
        }
        return false;
    }
};

//环形链表2
//假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。
///(x + y) * 2 = x + y + n (y + z)
//整理有：
//x = (n - 1) (y + z) + z
//y+z就是一圈的节点数 不管走了n-1圈 还是1圈 
//我们从根节点和z当前节点每次都走一个节点，一定会在入圈的第一个节点//相遇
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        //从相遇节点 和 头结点 分别开始走 相遇的位置就是入环的第一个节点
        ListNode*slow=head,*fast=head;
        //寻找相交节点
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;//fast->next不能为空
            if(slow==fast)
            {
                ListNode*index1=head;
                ListNode*index2=slow;
                while(index1!=index2)
                {
                    index1=index1->next;
                    index2=index2->next;
                }
                return index1;
            }
        }
        //slow或者fast为空了 证明没有环
        return nullptr;
        
    }
};

//删除有序链表中的重复节点
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head==nullptr)
        {
            return nullptr;
        }
        ListNode*cur=head;
        ListNode*last=head;
        while(last)
        {
            if(last && last->val==cur->val)
            {
                //相等 last往后走
                //找不相等的
                last=last->next;
            }
            else
            {
            //不相等
                cur->next=last;
                cur=last;
                last=last->next;
            }
        }
        //last为空了
        cur->next=nullptr;
        return head;
    }
};
